#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
	bool exist(vector<vector<char>>& board, string word)
	{
		int rowLength = board.size(), colLength = board[0].size();
		for (int row = 0; row < rowLength; row++)
			for (int col = 0; col < colLength; col++)
				if (board[row][col] == word[0] && dfs(row, col, 0, board, word))
					return true;
		return false;
	}

private:
	bool dfs(int row, int col, int idx, vector<vector<char>>& board, string& word)
	{
		if (idx == word.size()) return true;
		if (row < 0 || row == board.size() ||
				col < 0 || col == board[0].size() ||
				board[row][col] != word[idx])
			return false;

		char& cur_ch = board[row][col];
		char temp = cur_ch;
		cur_ch = '#';

		bool res = dfs(row - 1, col, idx + 1, board, word) ||
			dfs(row + 1, col, idx + 1, board, word) ||
			dfs(row, col + 1, idx + 1, board, word) ||
			dfs(row, col - 1, idx + 1, board, word);

		cur_ch= temp;

		return res;
	}
};

int main()
{
	Solution solu;
	vector<vector<char>> board = { { 'a', 'a' } };
	string word = "aaa";
	solu.exist(board, word);
	return 0;
}
